//
// Created by win10 on 2024/11/13.
//
// 链式结构的 栈
// 头节点 ==》 an ==> an-1 ==> ... ==> a1
//           栈顶                     栈底
// 所有的操作（插入、删除），都会在栈顶进行 换句话来说
// 所有节点的插入或者删除 都在 头节点之后进行

#include <math.h>
#include <stdlib.h>
#include <stdio.h>

// 1. 定义节点的结构
typedef struct
{
    // 数据域
    int data; // ElemType data
    // 指针域
    struct Node * next; // 指针变量的类型是什么？ 指针指向谁 ==> 下一个节点 Node 类型保持一致
}SNode; // stack ==> snode

// 2. 定义头节点的结构
typedef struct
{
    // 栈的相关信息
    int size; // 栈的长度
    // int capacity; // 栈的空间容量
    // 头指针
    struct Node * top; // 指向节点 和节点的数据类型保持一致
}Stack;

// 3. 创建/初始化 栈
// 返回一个栈的地址
Stack * createStack()
{
    // 为栈 开辟一个动态的空间 ==》 malloc
    Stack * s = (Stack *)malloc(sizeof(Stack));
    // 判断 栈的空间是否创建完毕
    if (s == NULL) // ==> 内存空间 占满了 创建栈失败了
    {
        printf("space is full");
        return NULL;
    }
    // 定义头指针和size, 此时头指针没有指向的节点 为空
    s->top = NULL;
    s->size = 0;
    return s; // s 是 栈的地址
}

// 4. 判断栈是否为空
int isEmpty(Stack * s)
{
    // 根据 size 来判断 ==》 =0 为空
    return s->top == 0;
}

// 5. 入栈操作
void push(Stack * s, int value)
{
    // 为新节点 分配空间
    SNode * newNode = (SNode *)malloc(sizeof(SNode));
    // 判断空间是否分配成功
    if (newNode == NULL)
    {
        printf("space is full");
        return;
    }
    // 为新节点的数据放入元素
    newNode->data = value;
    // 更新新节点的指针域
    newNode->next = s->top;
    // 更新头节点的指针域
    s->top = newNode;
    s->size++;
}

// 6. 出栈的操作
int pop(Stack * s)
{
    // 判断栈是否为空
    if (isEmpty(s))
    {
        printf("stack is empty");
        return -1; // -1 表示程序出错
    }
    // 定位到要被出栈的节点
    // 仅会出栈头节点之后的节点
    SNode * temp = s->top; // 用一个临时指针存储要出栈的节点
    int value = temp->data;
    // 头节点的指针域 更新
    s->top = temp->next; // s.top = s.top.next
    free(temp); // 释放 节点空间
    s->size--;
    return value;
}

// 7. 销毁栈
// 释放所有的空间
void destroyStack(Stack * s)
{
    // 栈不为空 一直出栈
    while(!isEmpty(s))
    {
        pop(s);
    }
    free(s);
    printf("stack has been destroyed\n");
}

void decimaltoOctal(int n)
{
    // 创建一个栈
    Stack * s = createStack();
    // 做一个循环 十进制转换成八进制
    while (n>0)
    {
        int remainder = n % 8;
        push(s, remainder);
        n /= 8;
    }
    // 八进制的值输出出来
    while (!isEmpty(s))
    {
        printf("%d", pop(s));
    }
    printf("\n");
    destroyStack(s);
}

int binarytoint(const char * binary)
{
    Stack * s = createStack();
    for(int i=0; binary[i]!='\0'; i++)
    {
        push(s, binary[i]-'0');
    }
    int decimal = 0;
    int position =0;
    while (!isEmpty(s))
    {
        int bit = pop(s);
        decimal = decimal + bit * pow(2,position);
        position++;
    }
    printf("%d\n", decimal);
    return decimal;

}

int factorial(int n) // 4
{
    Stack * s = createStack();

    int result = 1; // 出口

    // 递归
    for (int i = n; i >= 1; i--) // 4
    {
        push(s, i);
    }

    // 出栈 并 计算
    while (!isEmpty(s))
    {
        result *= pop(s);
    }
    destroyStack(s);
    return result;
}

int main(void)
{
    // Stack * s = createStack();
    // // 入栈
    // push(s, 1);
    // push(s, 2);
    // push(s, 3);
    // // 出栈
    // printf("%d\n", pop(s));
    // printf("%d\n", pop(s));
    // printf("%d\n", pop(s));
    decimaltoOctal(159);
    const char * binary = "1010";
    binarytoint(binary);
    printf("%d\n", factorial(4));
}